package 经典排序算法;

import java.util.ArrayList;
import java.util.Scanner;

/**
 * @ClassName : 基数排
 * @Author : 骆发茂
 * @Date: 2021/3/4 20:59
 * @Description :
 */
public class 基数排序_原数组顺序_从低位把各个数排序再把高位排序 {
    public static void main(String[] args) {
    System.out.println("请输入一个串数字，以空格作为分割，我将为你排序");
        System.out.println("=================================");
    Scanner scanner = new Scanner(System.in);
    String strings = scanner.nextLine();
    String[] newstrings = strings.split(" ");
    int[] array = new int[newstrings.length];
    for (int i = 0; i < newstrings.length; i++) {
        array[i] = Integer.parseInt(newstrings[i]);
    }
    System.out.println("==========原数组排序前为：===============");
    for (int j : array) {
        System.out.print(j + "  ");
    }
    System.out.println();
    System.out.println("==========数组排序后为：===============");
    RadixSort(array);
    for (int j : array) {
        System.out.print(j + "  ");
    }
    System.out.println();
}

    public  static int[] RadixSort(int[] array){
        if (array.length == 0) {
            return array;
            /*      if (array == null || array.length < 2)
            return array;*/

        }
        //先算出最大数的位数
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            max = Math.max(max,array[i]);//循环数组，能找到最大的
        }
        /*获取max的位数*/
        int maxdigit = 0;
        while (max!=0){
            max=max/10;
            maxdigit++;
        }
        int mod = 10,div = 1;
        ArrayList<ArrayList<Integer>>bucketList = new ArrayList<ArrayList<Integer>>();
        for (int i = 0; i < 10; i++)
            bucketList.add(new ArrayList<Integer>());
        for (int i = 0; i < maxdigit; i++, mod *= 10, div *= 10) {
            for (int j = 0; j < array.length; j++) {
                int num = (array[j] % mod) / div;
                bucketList.get(num).add(array[j]);
            }
            int index = 0;
            for (int j = 0; j < bucketList.size(); j++) {
                for (int k = 0; k < bucketList.get(j).size(); k++)
                    array[index++] = bucketList.get(j).get(k);
                bucketList.get(j).clear();
            }
        }
        return array;
    }
}
